package test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Marioszk
 * 字符串最大公因子
 * lettcode 1071
 */
public class MaxCommonStr_字符串最大公因子 {

    public static void main(String[] args) {
        String str1 = "ABABABAB";
        String str2 = "ABAB";
        System.out.println(gcdOfStrings2(str1, str2));
    }

    public static String gcdOfStrings(String str1, String str2) {
        String shortStr = str1.length() < str2.length() ? str1 : str2;
        String longStr = str1.length() < str2.length() ? str2 : str1;
        String res = "";
        if (!longStr.contains(shortStr)) {
            return res;
        }

        int longLen = longStr.length();
        int shortLen = shortStr.length();
        if (longLen % shortLen != 0) {
            return res;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < longLen / shortLen; i++) {
            sb.append(shortStr);
        }
        if (longStr.equals(sb.toString())) {
            return shortStr;
        }

        char[] charArr = shortStr.toCharArray();
        Character first = charArr[0];
        int sameIndex = -1;
        List<Integer> sameIndexList = new ArrayList<>();
        for (int i = 1; i < charArr.length; i++) {
            if (first == charArr[i]) {
                sameIndexList.add(i);
            }
        }
        List<String> patterns = new ArrayList<>();
        if (sameIndexList.size() == 0) {
            patterns.add(shortStr);
        }

        List<String> tList = new ArrayList();
        for (int i = 0; i < sameIndexList.size(); i++) {
            tList.add(shortStr.substring(0, sameIndexList.get(i)));
        }
        int len = shortStr.length();

        for (int i = tList.size() - 1; i >= 0; i--) {
            if (len % tList.get(i).length() != 0) {
                continue;
            }
            StringBuilder shortSb = new StringBuilder();
            for (int j = len / tList.get(i).length() - 1; j >= 0; j--) {
                shortSb.append(tList.get(i));
            }
            if (shortStr.equals(shortSb.toString())) {
                patterns.add(tList.get(i));
            }
        }

        if (patterns.size() == 0) {
            return "";
        }
        for (int i = 0; i < patterns.size(); i++) {
            if (longLen % patterns.get(i).length() != 0) {
                continue;
            }
            StringBuilder longSb = new StringBuilder();
            for (int j = 0; j < longLen / patterns.get(i).length(); j++) {
                longSb.append(patterns.get(i));
            }
            if (longStr.equals(longSb.toString())) {
                return patterns.get(i);
            }
        }
        return "";
    }

    public static String gcdOfStrings2(String str1, String str2) {
        int len1 = str1.length(), len2 = str2.length();
        String T = str1.substring(0, gcd(len1, len2));
        if (check(T, str1) && check(T, str2)) {
            return T;
        }
        return "";
    }

    public static boolean check(String t, String s) {
        int lenx = s.length() / t.length();
        StringBuffer ans = new StringBuffer();
        for (int i = 1; i <= lenx; ++i) {
            ans.append(t);
        }
        return ans.toString().equals(s);
    }

    public static int gcd(int a, int b) {
        int remainder = a % b;
        while (remainder != 0) {
            a = b;
            b = remainder;
            remainder = a % b;
        }
        return b;
    }
}
